class Solution {
    //回溯法
    //可以定义一个与字符矩阵相同大小的布尔矩阵，用于标识是否已经进入过该格
    //时间复杂度O(3^K *MN)k为需要搜索的字符串长度
    //空间复杂度O(k)
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(board.empty() || word.empty())  return false;

        int boardLength = board.size();
        int boardColumn = board[0].size();

        //布尔矩阵
        bool* visited = new bool[boardLength * boardColumn];
        memset(visited, 0, boardLength * boardColumn);  //memst赋初值

        //选择出发点
        for(int i = 0; i < boardLength; ++i){
            for(int j = 0; j < boardColumn; ++j){
                if(Search(board, word, i, j, 0, visited))  return true;
            }
        }

        return false;
    }

    bool Search(vector<vector<char>>& board, string &word, int i, int j, int w, bool* visited){
        //如果下标越界、值不匹配或已遍历过，则返回false
        if(i < 0 || j < 0 || i > (board.size() - 1) || j > (board[0].size() - 1) || visited[i*board[0].size() + j])
            //要注意先进行越界检查
            return false;
        
        if(board[i][j] != word[w]){
            return false; 
        }
        visited[i*board[0].size() + j] = true;  //找到了合适的点

        if(word.size() - 1 == w) return true;  //用字符串下标表示搜索进度

        if(
            Search(board, word, i, j + 1, w + 1, visited) ||
            Search(board, word, i + 1, j, w + 1, visited) ||
            Search(board, word, i - 1, j, w + 1, visited) ||
            Search(board, word, i, j - 1, w + 1, visited)
        )
        {
            return true;
        }else{
            visited[i*board[0].size() + j] = false;  //这是一条不匹配的路径，将布尔矩阵恢复原样
            return false;
        }
    }
};